package 剑指offer.数学;

import java.util.ArrayList;

/*
把只包含质因子2、3和5的数称作丑数（Ugly Number）。
例如6、8都是丑数，但14不是，因为它包含质因子7。
习惯上我们把1当做是第一个丑数。
求按从小到大的顺序的第N个丑数。
 */
public class 第49题丑数 {

    /*
    最暴力的方法当然就是一直循环 N 次取出第 index 个丑数。不用试，一定会超时的

    为了缩短时间，必须每一次循环计算的数据都是丑数才行，为了实现这一点需要两个操作
        1. 只进行当前数据的乘 2、乘 3、乘 5操作（因为丑数乘丑数结果一定是丑数）
        2. 暂存当前计算结果的最小值（该规则是为了让暂存数组有序）
        3. 要确保存入数组里面的各个丑数是有序的
        4. 之前提到的用得到的每一个丑数去产生下一个丑数是不全面的，应该是
            借助 2、3、5 的每一个丑数去更新下一个丑数，需要有指针来辅助执行？？

    那么为了实现有序，必须分别处理用来乘2、乘3、乘5 的被乘数
     */
    public static int GetUglyNumber_Solution(int index) {
        if (index <= 0)
            return 0;
        // 该数组只存储丑数，一共存储 index 个，最后一个元素就是第 index 个丑数
        int[] help = new int[index];
        help[0] = 1;// 第一个丑数一定是 1
        int nextUglyIndex = 1; // 下一个丑数的索引
        // 记录当前丑数的位置，若发现
        int T2 = 0;
        int T3 = 0;
        int T5 = 0;
        while (nextUglyIndex < index) {
            // 为了按照顺序生成丑数，计算出下一个丑数后，只取最小的那一个存入数组
            int min = min(help[T2] * 2, help[T3] * 3, help[T5] * 5);
            help[nextUglyIndex] = min;
            // 若发现当前位置的丑数乘上自己的倍数小于等于 min
            // 就说明其他位置的丑数需要在下一次作为 min 值被存储到数组中
            // 于是让自己的 T 值加一，自己的 T 值变大后，在下一次的计算中自己就不会再是 min 了
            // 这样的话，就不会出现只有 2 的倍数的丑数一直存入数组里面，而3、5没有机会

            if (help[T2] * 2 <= min) {   // ====> 要给别人机会，就得把自己增大
                T2++;
            }
            if (help[T3] * 3 <= min) {
                T3++;
            }
            if (help[T5] * 5 <= min) {
                T5++;
            }
            nextUglyIndex++;
        }
        return help[nextUglyIndex - 1];
    }

    public static int min(int t2, int t3, int t5) {
        return Math.min(Math.min(t2, t3), t5);
    }

    public static void main(String[] args) {
        System.out.println(GetUglyNumber_Solution(11));
    }

    public static int GetUglyNumber_Solution2(int n) {

        if (n <= 0)
            return 0;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        int i2 = 0, i3 = 0, i5 = 0;
        while (list.size() < n)//循环的条件
        {
            int m2 = list.get(i2) * 2;
            int m3 = list.get(i3) * 3;
            int m5 = list.get(i5) * 5;
            int min = Math.min(m2, Math.min(m3, m5));
            list.add(min);
            if (min == m2)
                i2++;
            if (min == m3)
                i3++;
            if (min == m5)
                i5++;
        }
        return list.get(list.size() - 1);
    }
}
